In the recent literature of Artificial Intelligence, an intensive researcheffort has been spent, for various algebras of qualitative relations used inthe representation of temporal and spatial knowledge, on the problem ofclassifying the computational complexity of reasoning problems for subsets ofalgebras. The main purpose of these researches is to describe a restricted setof maximal tractable subalgebras, ideally in an exhaustive fashion with respectto the hosting algebras. In this paper we introduce a novel algebra forreasoning about Spatial Congruence, show that the satisfiability problem in thespatial algebra MC-4 is NP-complete, and present a complete classification oftractability in the algebra, based on the individuation of three maximaltractable subclasses, one containing the basic relations. The three algebrasare formed by 14, 10 and 9 relations out of 16 which form the full algebra.
展开▼
